#include"undigraph.h"
#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
const int inf = 10000;//定义一个无穷大
Undigraph::Undigraph(const string& filename){
//从文件读取V&E，初始化图，不过这个是无向图
    fstream f;
    f.open(filename,ios::in);
    if(!f){
        std::cerr<<"can't open file"<<endl;
        exit(-1);
    }
    int V,E;    //获取顶点和边的数目
    f>>V>>E;
    this->V=V;
    this->E=E;
    this->_adj=new Undigraph::Vertextable[V];  //新建接邻多重表
    for(int i=0;i<V;i++){
        _adj[i].data=i;
    }
    for(int i=0;i<E;i++){//将每一个边读入
        int leftpoint,rightpoint;  //读取边的两边
        double weight;
        f>>leftpoint>>rightpoint;
        f>>weight;
        Undigraph::Sidetable *edge=new Undigraph::Sidetable(leftpoint,rightpoint);//新建一条边
        edge->weight=weight;
        
        //链接边和顶点表中的点
stage1:
        if(!_adj[leftpoint].firstedge){//如果顶点表中尚未有具体指向，则指向刚新建的对象
            _adj[leftpoint].firstedge=edge;
        }else{              //如果已经有具体指向，则依次看看iv或者jv是否和leftpoint相同

            Sidetable *p=_adj[leftpoint].firstedge;
            while(1){
                if(p->ivex==leftpoint){
                    if(!p->ilink){          //找到了最后一个节点，则添加进去
                        p->ilink=edge;
                        goto stage2;        //跳出循环
                    }
                    p=p->ilink;
                    continue;
                }
                if(p->jvex==leftpoint){
                    if(!p->jlink){          //找到了最后一个节点，则添加进去
                        p->jlink=edge;
                        goto stage2;        //跳出循环
                    }
                    p=p->jlink;
                    continue;
                }
            } 
        }
stage2:     
        if(!_adj[rightpoint].firstedge){//如果顶点表中尚未有具体指向，则指向刚新建的对象
            _adj[rightpoint].firstedge=edge;
        }else{              //如果已经有具体指向，则依次看看iv或者jv是否和rightpoint相同

            Sidetable *p=_adj[rightpoint].firstedge;
            while(1){
                if(p->ivex==rightpoint){
                    if(!p->ilink){          //找到了最后一个节点，则添加进去
                        p->ilink=edge;
                        goto finish;        //跳出循环
                    }
                    p=p->ilink;
                    continue;
                }
                if(p->jvex==rightpoint){
                    if(!p->jlink){          //找到了最后一个节点，则添加进去
                        p->jlink=edge;
                        goto finish;        //跳出循环
                    }
                    p=p->jlink;
                    continue;
                }
            } 
        }
finish:
      continue;  
    }
    cout<<"build ok"<<endl;
}
vector<int> Undigraph::dijkstra(int source,int target){
    vector<int> result;
    if(source>=V || target>=V){
        cerr<<"error Vertex"<<endl;
        return result;
    }
    
    priority_queue<point*,vector<point*>,cmp> U;//用来存放U队列，因为他可以自动找出最小的值
    //1.将起点放入
    point *(*arr)=new point*[V];//这个是为了方便的松弛边的数组，因为如果直接用有限队列的话不好调整
    int *status = new int[V]{0}; //记录哪些点已经找出最小路径，以防止在松弛的那一步重复松弛
    arr[source]=new point(source,0);//起点和起点自己的权重为0
    status[source]=1;
    for(int i=0;i<V;i++){
        //将还没加入的点，其权值设置为无限大,并且加入到U中 
        if(i!=source){
            arr[i]=new point(i,inf);
            U.push(arr[i]);
        }
    }
    
    //2.先将和起点相连的点以及边放入优先队列
    Sidetable *p=_adj[source].firstedge;
    
    while(p){
        if(source==p->jvex){//将和起点相连的另一端放入优先队列
            arr[p->ivex]->Weight=p->weight;
            p=p->jlink;
        }else{
            arr[p->jvex]->Weight=p->weight;
            p=p->ilink;
        }
    }
    while(U.size()){
    //选取距离最小的一个点
    point *minVerx=U.top();U.pop();  
    status[minVerx->Vertex] =1; 
    //松弛和这个最小的一个点相关的边
    p=_adj[minVerx->Vertex].firstedge;
    while(p){
        if(minVerx->Vertex==p->ivex){
            if(status[p->jvex]==0)//如果已经被放到结果队列里面则寻找下一个
            {
                printf("%d-%d 松弛\n",minVerx->Vertex,p->jvex);
                arr[p->jvex]->Weight=min(arr[p->jvex]->Weight,minVerx->Weight+p->weight);
            }
            p=p->ilink;
        }else{
            if(status[p->ivex]==0)//如果已经被放到结果队列里面则寻找下一个
            {
                printf("%d-%d 松弛\n",minVerx->Vertex,p->ivex);
                arr[p->ivex]->Weight=min(arr[p->ivex]->Weight,minVerx->Weight+p->weight);
            }
            p=p->jlink;
        }
    }
    for(int i=0;i<V;i++){
        cout<<arr[i]->Weight<<"\t";
    }cout<<endl;/**/
    }
    
}